Міністерство Освіти та Науки України
Національний Університет “Львівська Політехніка”
Кафедра ЕОМ
Курсова робота
з дисципліни: “ Паралельні та розподілені обчислення ”
на тему:
«Паралельне виконання операцій множення матриць»
Завданння
Задаються дві матриці А (розмірністю n1*n2) та В (розмірністю n2*n3) :
n1=3П, n2=2І, n3=4Б – КІ-42, де 3П=И(160), 2І=А(64), 4Б=К(307)
n1=160, n2=64, n3=307
Отже маємо матрицю А(160*64) та матрицю В(64*307)
Розробити та описати алгоритм множення матриць А*В на структурі яка задається виразом:
5b-12b-6b-11b-8b-1b-3b-13b – КІ-42, де «nb»- номер букви П.І.Б студента.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
Г
Р
И
Ц
Ю
К
П
А
В
Л
О
О
Л
Е
К
С
А
Н
Д
Р
О
В
И
Ч
7
8
1
3
5
2
4
9
Отримаємо – ЮОКЛАГИЕ
Для ЮОКЛАГИЕ отримаємо 63, 250, 47, 212, 27, 74, 91, 171. Даний набір чисел записуємо у стовпець і переводимо у двійкове 8-ми розрядне число:
063 -
00111111
250 -
11111010
047 -
00101111
212 -
11010100
027 -
00011011
074 -
01001010
091 -
01011011
171 -
10101011
В отриманій двійковій матриці одиниці що розташовані на головній діагоналі замінюємо на 0.
0
0
1
1
1
1
1
1
=>
0
0
1
1
1
1
1
1
1
1
1
1
1
0
1
0
1
0
1
1
1
0
1
0
0
0
1
0
1
1
1
1
0
0
0
0
1
1
1
1
1
1
0
1
0
1
0
0
1
1
0
0
0
1
0
0
0
0
0
1
1
0
1
1
0
0
0
1
0
0
1
1
0
1
0
0
1
0
1
0
0
1
0
0
1
0
1
0
0
1
0
1
1
0
1
1
0
1
0
1
1
0
0
1
1
0
1
0
1
0
1
1
1
0
1
0
1
0
1
0
Отримана матриця розміру 8*8 є матрицею зв’язків орієнтованого графу, вершини якого це процесори а напрямлені дуги це напрямлені лінії зв’язку між процесорами. На основі цієї матриці будується відповідний їй граф що характеризує конкретну 8-ми процесорну систему (структуру) із напрявленими зв’язками між вершинами.
Для цієї структури визначити час виконання алгоритму, відсоток послідовної частини алгоритму та ефективність алгоритму для значень, співвідношення часових параметрів та тип початкового завантаження визначаються за правилами:
3.1. Тип початкового завантаження даних type:
, де Zi цифри номера залікової книжки, n=1..k, де k – кількість цифр номера залікової книжки.
Zi=1009167, n=7
type=1(спільна пам’ять)
3.2. Співвідношення часових параметрів tU,tS,tP,tZ,tW:
tU – час виконання однієї операції множення;
tS - час виконання однієї операції сумування;
tP - час виконання однієї операції пересилання даних між процесорами;
tZ - час виконання операції завантаження одних даних;
tW - час виконання операції вивантаження одних даних.
tU=(Zk-3 +1)tS=(Zk-2 +1)tP=(Zk-1 +1)tZ=(Zk+1)tW, де Zi відповідна цифра номера залікової книжки, k -кількість цифр в номері залікової книжки.
tU=10tS=2tP=7tZ=8tW
Анотація
В даній курсовій роботі розроблено програмну реалізацію восьми процесорної паралельної системи зі спільною пам’яттю, яка виконує множення двох матриць розмірами 160х64 та 64х307. Також наводяться числові значення характеристик даної системи таких як ефективність, коефіцієнт відношення часу виконання паралельної частини програми і часу виконання всієї програми. Проведено також порівняння даного алгоритму з простим послідовним за такими основним ознаками, як час виконання однакової задачі на різних алгоритмах, ефективність. Алгоритм виконання множення 2-ох матриць реалізований на С++ з консольним інтерфейсом, та з використанням MPI.
Зміст
Вступ………………………………………………………………………………..…. 6
1. Теоретичний розділ………………………………………………………………... 7
1.1 Алгоритм перемноження матриці на матрицю на кільцевій структурі .....8
1.2 Інтерфейс передачі повідомлень……………………………………………10
2. Аналіз(розробка) граф-схеми алгоритму множення матриць……………...…… 12
3. Розробка функціональної схеми……………………………………………........... 16
4. Розрахунковий розділ………………………………………………………………18
5. Розробка програми викон...
